package com.zhang.heap;

import java.util.Arrays;

/**
 * @author zhang
 * @time 2022/03/05 07:49:00
 */
public class Heap {
    private int[] array = new int[10];
    private int size;

    public void insert(int item) {
        array[size++] = item;
        bubbleUp();

    }
    public void remove() {
        array[0] = array[--size];
        int index = 0;
        while (index <= size && !isValidParent(index)) {
            int largerChildIndex = largerChildIndex(index);
            swap(index,largerChildIndex);
            index = largerChildIndex;
        }

    }

    private int largerChildIndex(int index) {
        return leftChild(index) > rightChild(index) ? leftChildIndex(index) : rightChildIndex(index);
    }

    private boolean isValidParent(int index) {
        return array[index] >= leftChild(index) &&
                array[index] >= rightChild(index);
    }

    private int leftChild(int index) {
        return array[leftChildIndex(index)];
    }

    private int rightChild(int index) {
        return array[rightChildIndex(index)];

    }
    private int leftChildIndex(int index) {
        return index * 2 + 1;
    }

    private int rightChildIndex(int index) {
        return index * 2 + 2;
    }

    private void bubbleUp() {
        int index = size - 1;

        while (index > 0 && array[index] > array[parent(index)]) {
            swap(index, parent(index));
            index = parent(index);
        }
    }

    private int parent(int index) {
        return (index - 1) / 2;
    }

    private void swap(int index1, int index2) {
        int temp = array[index1];
        array[index1] = array[index2];
        array[index2] = temp;

    }
    private void swap(int[] arr,int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;

    }

    public void heapify(int[] array) {
        int lastParentIndex = array.length / 2 - 1;
        for (int i = lastParentIndex; i >= 0; i--) {
            heapify(array, i);
        }



    }

    private void heapify(int[] array, int index) {
        int largerIndex = index;

        int leftIndex = index * 2 + 1;
        if (leftIndex < array.length && array[leftIndex] > array[largerIndex]) {
            largerIndex = leftIndex;
        }

        int rightIndex = index * 2 + 2;
        if (rightIndex < array.length && array[rightIndex] > array[largerIndex]) {
            largerIndex = rightIndex;
        }
        if (index == largerIndex) {
            return;
        }
        swap(array,index,largerIndex);

        heapify(array,largerIndex);
    }

    public static void main(String[] args) {
        Heap heap = new Heap();
//        heap.insert(10);
//        heap.insert(5);
//
//        heap.insert(22);
//        heap.insert(4);
//        heap.remove();

        int[] array = {4, 2, 7, 9, 12, 5, 6};
        heap.heapify(array);
        System.out.println(Arrays.toString(array));
    }
}
